from typing import List
"""
15. 三数之和
https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
 

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

"""

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        先对数组进行排序
        之后使用双指针遍历，p1从0开始，之后是p2从1开始，寻找符合条件的结果
        """
        nums.sort()
        num_index_map=dict()
        for (i,num) in enumerate(nums):
            if num in num_index_map:
                num_index_map[num].append(i)
            else:
                num_index_map[num]=[i]

        # print(num_index_map)
        # nums.sort()
        result=[]
        p1=0
        last_v1=None
        last_v2=None
        while p1< len(nums)-1:
            p2=p1+1
            while p2<len(nums):
                target_val=-nums[p1] - nums[p2]
                if target_val in num_index_map:
                    target_indexs=num_index_map[target_val]
                    for ti in target_indexs:
                        if ti>p2:
                            result.append([nums[p1],nums[p2],nums[ti]])
                    # result.append([p1,p2,num_index_map])
                if last_v2 is not None:
                    while p2<len(nums) and last_v2==nums[p2]:
                        p2+=1
                last_v2=nums[p2]

                p2+=1

            if last_v1 is not None:
                while p1<len(nums)-1 and last_v1==nums[p1]:
                    p1+=1
            last_v1=nums[p1]

            p1+=1

        return result

if __name__ == '__main__':
    nums=[-1,0,1,2,-1,-4]
    sol=Solution()
    result=sol.threeSum(nums)
    print(result)